bef-> NO.43

Veröffentlicht am | Edited on

可能接下来一段时间里就不能一心一意学OI了，我落下的文化课可能是最多的。

突然想到一道题

[USACO07MAR]排名的牛Ranking the Cows

题目描述

Each of Farmer John’s N cows (1 ≤ N ≤ 1,000) produces milk at a different positive rate, and FJ would like to order his cows according to these rates from the fastest milk producer to the slowest.

FJ has already compared the milk output rate for M (1 ≤ M ≤ 10,000) pairs of cows. He wants to make a list of C additional pairs of cows such that, if he now compares those C pairs, he will definitely be able to deduce the correct ordering of all N cows. Please help him determine the minimum value of C for which such a list is possible.

FJ想按照奶牛产奶的能力给她们排序。现在已知有N头奶牛（1 ≤ N ≤ 1,000）。FJ通过比较，已经知道了M（1 ≤ M ≤ 10,000）对相对关系。每一对关系表示为“X Y”，意指X的产奶能力强于Y。现在FJ想要知道，他至少还要调查多少对关系才能完成整个排序。

输入输出格式

输入格式：

Line 1: Two space-separated integers: N and M

Lines 2..M+1: Two space-separated integers, respectively: X and Y. Both X and Y are in the range 1…N and describe a comparison where cow X was ranked higher than cow Y.

输出格式：

Line 1: A single integer that is the minimum value of C.

输入输出样例

输入样例#1：

1
2
3
4
5
6
5 5
2 1
1 5
2 3
1 4
3 4

输出样例#1：

1
3

说明

From the information in the 5 test results, Farmer John knows that since cow 2 > cow 1 > cow 5 and cow 2 > cow 3 > cow 4, cow 2 has the highest rank. However, he needs to know whether cow 1 > cow 3 to determine the cow with the second highest rank. Also, he will need one more question to determine the ordering between cow 4 and cow 5. After that, he will need to know if cow 5 > cow 3 if cow 1 has higher rank than cow 3. He will have to ask three questions in order to be sure he has the rankings: “Is cow 1 > cow 3? Is cow 4 > cow 5? Is cow 5 > cow 3?”

题解

bitset传递闭包。

我突然想到之所以我错的原因是

1
2
for(int i = 1 ; i <= n ; ++i)
    s[i] |= 1 << i;

无话可说。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
#define maxn 1005
std::vector<int> G[maxn]; // positive , negetive
int n , m , ans , d[maxn];
bool vis[maxn][maxn];
std::bitset<maxn> s[maxn];
inline void Toposort()
{
    std::queue<int> q;
    for(int i = 1 ; i <= n ; ++i)
        if(!d[i])   q.push(i);
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        for(int i = 0 ; i < (int)G[k].size() ; ++i){
            int v = G[k][i];
            s[v] |= s[k];
            --d[v];
            if(!d[v])   q.push(v);
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= m ; ++i){
        int x , y;
        scanf("%d%d",&x,&y);
        if(vis[x][y] || vis[y][x])  continue;
        G[y].push_back(x);
        vis[x][y] = vis[y][x] = true;
        ++d[x];
    }
    for(int i = 1 ; i <= n ; ++i)
        s[i][i] = 1;
    Toposort();
    for(int i = 1 ; i <= n ; ++i)
        ans += s[i].count();//include itself , so it is n
    ans = n * (n - 1) / 2 + n - ans;
    printf("%d",ans);
}